Klub Prawoskrętnych Kierowców
Limit pamięci: 32 MB
Dana jest prostokątna mapa miasta złożona z kwadratowych
pól ( i ). Wiersze
kwadratowych pól tworzących mapę są ponumerowane kolejno od góry do dołu
liczbami od do , a kolumny od lewej do prawe, kolejno
od do . Każde pole jest albo wolne albo zablokowane.
Ruch kołowy jest dozwolony tylko po wolnych polach. Z każdego wolnego pola można
przejechać na wolne pole przyległe (tzn. takie, które ma z danym polem wspólny
bok), nie można jednak zawracać, to znaczy bezpośrednio po przejechaniu z pola
na przyległe pole wrócić na .
Klub Prawoskrętnych Kierowców złożył zamówienie na program komputerowy, który
dla dowolnych dwóch różnych pól oraz rozstrzyga, czy
można dojechać od punktu do nie wykonując ani jednego
skrętu w lewo, a jeśli tak, znajduje jedną taką drogę o minimalnej długości.
Długość drogi jest to liczba wszystkich jej pól. Do drogi od do
zaliczamy również pola oraz .
Zadanie
Ułóż program który:
- wczytuje ze standardowego wejścia dane o prostokątnej sieci pól (tzn.
liczbę wierszy , liczbę kolumn i stan każdego pola, a
następnie współrzędne dwóch różnych pól i ;
- rozstrzyga, czy istnieje droga bez skrętów w lewo od pola do
i jeśli nie, to zapisuje w standardowym wyjściu jedno słowo
NIE, a jeśli tak, to znajduje jedną taką drogę o minimalnej długości i
zapisuje ją w standardowym wyjściu. Jeśli chociaż jedno z pól ,
nie jest wolne, to odpowiedzią jest NIE.
Wejście
W standardowym wejściu znajdują się dwie liczby całkowite, oddzielone
pojedynczym odstępem: liczba wierszy oraz liczba kolumn
. W każdym z kolejnych wierszy pliku znajduje się opis
odpowiedniego kolejnego wiersza mapy w postaci jednego słowa o długości
utworzonego z cyfr i . Cyfra
oznacza, że odpowiednie pole jest wolne a cyfra , że jest
zablokowane.
Następnie w jednym wierszu są zapisane dwie współrzędne pola
oddzielone pojedynczym odstępem: numer wiersza nie większy niż oraz
numer kolumny nie większy niż , a w kolejnym wierszu są zapisane, w
taki sam sposób, dwie współrzędne pola .
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego
sprawdzać.
Wyjście
W standardowym wyjściu należy zapisać:
- albo jedno słowo NIE, gdy nie istnieje droga bez skrętów w lewo od
do , lub przynajmniej jedno z pól ,
jest zablokowane,
- albo opis jednej drogi bez skrętów w lewo od do o
minimalnej długości; w tym przypadku w pierwszym wierszu należy wpisać długość
drogi , a w każdym z kolejnych wierszy dwie współrzędne
kolejnego pola drogi oddzielone pojedynczym odstępem.
Przykłady
Dla danych wejściowych:
8 9
010011101
011010101
000000000
111010101
101000100
111010101
000000000
101011111
2 6
1 3
poprawną odpowiedzią jest:
NIE
Dla danych wejściowych:
8 9
010011101
011010101
000000000
111010101
101000100
111010101
000000000
101011111
2 6
3 8
poprawną odpowiedzią jest:
12
2 6
3 6
4 6
5 6
5 5
5 4
4 4
3 4
3 5
3 6
3 7
3 8
Autor zadania: Piotr Chrząstowski-Wachtel.